#define ELEMENT_LIST_OK 0
#define ELEMENT_LIST_ERROR_NEXT 1
#include "list_forest.h"
# include <string.h>   /* memcpy */
# include <stdio.h>    /* printf */
# include <stdlib.h>   /* malloc */


typedef struct list_element list_element;

struct list_element{
	void* element;
	list_element* suivant;
};



struct list_forest_struct{
	void * value;
	list_element * element;
	list_forest father;
	list_forest brotherMostLeft;
	list_forest brotherRight;
	list_forest firstSon;

	void ( * copy_value ) ( const void * value , void ** pt );
	void ( * free_value ) ( void ** );
	void ( * copy_element ) ( const void * element , void ** pt );
	void ( * free_element ) ( void ** );
};




int list_forest_create ( list_forest * lfpt,
	void ( * copy_value ) ( const void * value , void ** pt ) ,
	void ( * free_value ) ( void ** ),
	void ( * copy_element ) ( const void * element , void ** pt ) ,
	void ( * free_element ) ( void ** ) ) {


	*lfpt =  malloc(sizeof(struct list_forest_struct));
	/**lfpt = malloc(sizeof(list_forest));
	if( lfpt == NULL)
		return FOREST_LIST_ERROR_MEMORY;


	*lfpt = lf;*/



	(*lfpt)->element = 0;
	(*lfpt)->value = 0;
	(*lfpt)->father = 0;
	(*lfpt)->brotherRight = 0;
	(*lfpt)->brotherMostLeft = 0;
	(*lfpt)->firstSon = 0;


	(*lfpt)->copy_value = copy_value;
	(*lfpt)->free_value = free_value;
	(*lfpt)->copy_element = copy_element;
	(*lfpt)->free_element = free_element;



	return FOREST_LIST_OK;
}

void free_list_element(list_forest * lfpt){
	list_element *le, *leSave;
	le = (*lfpt)->element;
	while(le != 0){
		leSave = le;
		(*lfpt)->free_element( ((*lfpt)->element)->element );
		free(leSave);
		le = le->suivant;
	}
}

int list_forest_destroy ( list_forest * lfpt) {
	if( (*lfpt)->value != 0 )
		(*lfpt)->free_value((*lfpt)->value);
	if( (*lfpt)->element != 0 )
		free_list_element(lfpt);

	return FOREST_LIST_OK;
}

int list_forest_is_empty ( list_forest lf) {
	if (lf->value == 0){
		return 1;
	} else {
		return 0;
	}
}








struct list_forest_position_struct{
	list_forest node;
	list_element * le;
};





int list_forest_position_create ( list_forest lf, list_forest_position *  lfp) {

	list_forest_position lfpStru = malloc(sizeof(struct list_forest_position_struct));

	*lfp = malloc(sizeof(list_forest_position));
	*lfp = lfpStru;

	(*lfp)->node = lf;
	(*lfp)->le = 0;



	return FOREST_LIST_OK;
}



/* remonte toute la foret jusqu'au premier noeud et renvoir son adresse*/
int get_premierNoeud ( list_forest_position *lfp)	{
	while(list_forest_position_has_father( *lfp )  || list_forest_position_has_left_son ( *lfp ) )
	{
		if(list_forest_position_has_father( *lfp ) )
		{
			(*lfp)->node = ( (*lfp)->node)->father;
		}
		else if(list_forest_position_has_left_son ( *lfp ))
		{
			(*lfp)->node = (*lfp)->node->brotherMostLeft;
		}
	}
	return FOREST_LIST_OK;
}


int list_forest_empty_aux (list_forest_position lfp) {
	list_forest_position lfpAux;
	do{
		/* on libere la memoire alloue pour la balise et les attributs */
		list_forest_destroy(&(lfp->node));

		/*si la list forest a des fils, on s'en occupe */
		if( (lfp->node)->firstSon != 0)
		{
			list_forest_position_duplicate(lfp, &lfpAux);/*on pars du meme endroit puis on descend sur le firstson */
			list_forest_position_left_son(lfpAux);
			list_forest_empty_aux(lfpAux);
			list_forest_position_destroy(&lfpAux);/*on detruit ll'espace alloué*/
		}

		list_forest_position_next_brother(lfp);
	}while ( lfp->node != 0 );

	return FOREST_LIST_OK;
}

int list_forest_empty ( list_forest lf ) {

	/*on part du noeud le plus haut dans l'arbre et le plus a gauche*/
	list_forest_position lfp;
	list_forest_position_create(lf,&lfp);
	get_premierNoeud( &lfp );

	list_forest_empty_aux(lfp);
	return FOREST_LIST_OK;
}


int list_forest_position_duplicate ( list_forest_position  lfp, list_forest_position * lfpCopie) {

	list_forest_position_create ( lfp->node, lfpCopie);
	return FOREST_LIST_OK;
}


int list_forest_position_destroy ( list_forest_position* lfppt)
{
	free(*lfppt);
	*lfppt = 0;
	return FOREST_LIST_OK;
}



int list_forest_position_has_father ( list_forest_position lfp) {
	return ( (lfp->node)->father != 0);
}

int list_forest_position_father ( list_forest_position lfp){
	if(list_forest_position_has_father(lfp))
		lfp->node = (lfp->node)->father;


	return FOREST_LIST_OK;
}



int list_forest_position_has_left_son ( list_forest_position lfp) {
	return ( (lfp->node)->firstSon != 0);
}

int list_forest_position_left_son ( list_forest_position lfp) {
	if(list_forest_position_has_left_son(lfp))
		lfp->node = lfp->node->firstSon;
	
	return FOREST_LIST_OK;
}



int list_forest_position_has_next_brother ( list_forest_position lfp) {
	return ( (lfp->node)->brotherRight != 0);
}

int list_forest_position_next_brother ( list_forest_position lfp) {
	if(list_forest_position_has_next_brother(lfp))
		lfp->node = lfp->node->brotherRight;
	
	return FOREST_LIST_OK;
}







	void * list_forest_position_value ( list_forest_position lfp) {
		return (lfp->node)->value;
	}








	/* MODIFICATION of the FOREST */

	void list_forest_destroy_node_and_all_sons_and_brothers ( list_forest_position lfpPere ) {
		list_forest_position lfpFils;
		list_forest_position_duplicate(lfpPere, &lfpFils);
		list_forest_position_left_son(lfpFils);

		while(lfpFils != 0){
			list_forest_destroy_node_and_all_sons_and_brothers(lfpFils);
			if(list_forest_position_has_next_brother(lfpFils))
				list_forest_position_next_brother(lfpFils);
		}

		list_forest_destroy(&(lfpPere->node));
		free(lfpPere->node);

		list_forest_position_destroy(&lfpFils);

	}





	int list_forest_add_next_brother ( list_forest_position lfp,
		const void * value ) {

		list_forest newLf;
		list_forest_create (  &newLf, (lfp->node)->copy_value,
			(lfp->node)->free_value, (lfp->node)->copy_element, (lfp->node)->free_element );

	/* on ajoute la value */
		newLf->copy_value(value, &(newLf->value) );

	if( (lfp->node)->brotherMostLeft == 0)/*si le noeud lfp->node n'a pas de brothermostleft, c'est qu'il l'est lui meme*/
		newLf->brotherMostLeft = lfp->node;
	else/* sinon, newLF prend le meme brother most left*/
		newLf->brotherMostLeft = (lfp->node)->brotherMostLeft;


	newLf->father = (lfp->node)->father;/* les deux  noeuds auront le meme pere*/

	newLf->brotherRight = (lfp->node)->brotherRight;/* on insere le frere entre les deux noeuds*/
	(lfp->node)->brotherRight = newLf;

		return FOREST_LIST_OK;
	}

/** Remove the next brother node (and all its descendants) of the indicated node.
	Uses free_value (and free_element whenever needed).
 **/
	int list_forest_position_next_brother_remove ( list_forest lp, list_forest_position lfp) {

		list_forest_position lfpSave;
		list_forest_position_duplicate( lfp,  &lfpSave);

		if( (lp->brotherRight)->brotherRight != 0 ) {
			lp->brotherRight = (lp->brotherRight)->brotherRight;
		}
		else {
			lp->brotherRight = 0;
		}

		/* on detruit tout le noeud et ses fils*/
		list_forest_position_next_brother(lfpSave);
		list_forest_destroy_node_and_all_sons_and_brothers ( lfpSave );


	/*on fini par liberer les ressources alloué par la structure*/
		list_forest_position_destroy(&lfpSave);

		return FOREST_LIST_OK;
	}

/** Add a node as lefy son.
	Create the root on an empty forest.
	Uses copy_value
**/
	int list_forest_add_left_son ( list_forest_position lfp, const void * value ) {

	list_forest newLf;
	list_forest_position lfpAux; /* lfpAux pour l'ancien fils (si present) */

	if(lfp->node->value != 0){
		list_forest_create ( &newLf, lfp->node->copy_value, lfp->node->free_value, lfp->node->copy_element, lfp->node->free_element );	/* On cree une nouvelle list_forest avec les fonction du pere */
		newLf->copy_value(value, &(newLf->value)); /* On initialise la value dans la nouvelle list forest */
		newLf->father = lfp->node; /* on fait pointer le fils sur son pere*/



		if( list_forest_position_has_left_son(lfp) ){ /* on regarde si il a un fils */
			list_forest_position_duplicate(lfp,&lfpAux);
			list_forest_position_left_son(lfpAux);

			newLf->brotherRight = lfpAux->node; /* On met l'ancien fils a droite du nouveau */
			while(lfpAux->node != 0){
				lfpAux->node->brotherMostLeft = newLf;
				list_forest_position_next_brother(lfpAux);
			}

			list_forest_position_destroy(&lfpAux);
		}
			lfp->node->firstSon = newLf;/* on fait pointer le pere sur son nouveau fils*/

	}
	else {/* si le noeud racine n'a pas de valeur, on ajoute pas de nouveau noeud, et on rempli l'ancien */
		lfp->node->copy_value(value, &(lfp->node->value)); /* On initialise la value dans la nouvelle list forest */
	}

    return FOREST_LIST_OK;
}

/** Remove the left son node (and all its descendants) of the indicated node.
	Uses free_value (and free_element whenever needed).
**/
	int list_forest_position_left_son_remove ( list_forest lf,
		list_forest_position lfp) {

		list_forest_position lfpSave;
		list_forest_position_duplicate ( lfp,  &lfpSave);


	/* si il y a plus d'un fils, on enleve le premier, et on change le lien des autres vers le most left brother */
		if( ( lf->firstSon)->brotherRight != 0 ) {
		list_forest_position_left_son(lfp);/*on fait pointer lfp sur le premier fils que l'on doit supprimer*/
		(lfpSave->node)->firstSon = (lfp->node)->brotherRight;/*on fait pointer le pere sur le deuxieme fils*/

			list_forest_position_left_son(lfpSave);
		list_forest_position_next_brother(lfpSave);/* on fait pointer lfpSave sur le deuxieme fils*/

		list_forest_destroy_node_and_all_sons_and_brothers(lfp);/*on supprime le premier fils*/

		lfp->node = lfpSave->node;/*on fait pointer les deux listforest position sur le deuxieme fils*/

		(lfpSave->node)->brotherMostLeft = 0; /* lfpSave est le mostleftbrother*/

		/*on fait pointer les autres fils vers le deuxieme fils*/
			while(list_forest_position_has_next_brother(lfpSave)){
				list_forest_position_next_brother(lfpSave);
				(lfpSave->node)->brotherMostLeft = lfp->node;
			}
		}
	/* si il n'y a qu'un fils */
		else{
			list_forest_destroy_node_and_all_sons_and_brothers(lfp);
			(lfpSave->node)->firstSon = 0;
		}

		list_forest_position_destroy(&lfpSave);

		return FOREST_LIST_OK;
	}



	int list_forest_position_has_element ( list_forest_position lfp) {
		return ( (lfp->node)->element != 0 );
	}

/** Move onto the next element (or out of the list if it was the last element). **/
	int list_forest_position_element_next ( list_forest_position lfp) {
	/* Cas ou on a pas encore parcouru la liste d element */
		if(lfp->le == 0){
			if( (lfp->node)->element != 0 ){
				lfp->le = (lfp->node)->element;
				return ELEMENT_LIST_OK;
			}
		} else {
		/* Cas ou on a deja parcouru et il a un suivant */
			if(lfp->le->suivant != 0){
				lfp->le = lfp->le->suivant;
				return ELEMENT_LIST_OK;
			} else {
			/* Cas ou on a deja parcouru et il n y a pas de suivant */
				lfp->le = 0;
				return ELEMENT_LIST_ERROR_NEXT;
			}
		}
		return FOREST_LIST_OK;
	}

/** Return the curent element.
	Please note, it is the direct adresse, no copy is done
	(copy_element is not used). **/
	void * list_forest_position_element ( list_forest_position lfp) {
		return lfp->le->element;
	}


	int list_forest_add_element ( list_forest_position lfp,
		const void * element ) {

		list_element* maillon = (list_element*)malloc(sizeof(list_element));
		maillon->suivant = 0;
		lfp->node->copy_element(element, &(maillon->element) ); /* on copie la value de l'element dans le nouveau maillon */

		list_element* maillonAux = 0;

		if(lfp->node->element != 0){
			maillonAux = lfp->node->element;
			while(maillonAux->suivant != 0){
				maillonAux = maillonAux->suivant;
			}
			maillonAux->suivant = maillon;
		}
		else{

			(lfp->node)->element = maillon;
		}

		return FOREST_LIST_OK;
	}


	void list_element_fprint(FILE * file, list_forest_position lfp, void ( * print_element ) ( FILE * , void * )){
		if(list_forest_position_has_element(lfp)){
			if(lfp->le == 0){
				list_forest_position_element_next(lfp);

			}
			while(lfp->le->suivant != 0){
				fprintf(file, " ");
				print_element(file, lfp->le->element);
				list_forest_position_element_next(lfp);
			}
			fprintf(file, " ");
			print_element(file, lfp->le->element);

		}
	}

/**
/** Printing.
    Comes handy when debugging. **/
	void list_forest_fprint_aux ( FILE * file,
		list_forest lf,
		void ( * print_value ) ( FILE * , void * ) ,
		void ( * print_element ) ( FILE * , void * ) , int nbTabulation ){

		int i;
		list_forest_position lfp;
		list_forest_position_create(lf, &lfp);


		for(i = 0 ; i < nbTabulation ; i++){
			fprintf(file," ");
		}

		if(lf->value != 0)
			print_value(file,lf->value);
		fprintf(file," [");

			list_element_fprint(file, lfp, print_element);

			fprintf(file," ]");




			if( list_forest_position_has_left_son(lfp) ) {
				fprintf(file,"\n");
				list_forest_fprint_aux(file, (lf->firstSon), print_value, print_element,nbTabulation+1);
			}
			if( list_forest_position_has_next_brother(lfp) ){
				fprintf(file,"\n");
				list_forest_fprint_aux(file, (lf->brotherRight), print_value, print_element,nbTabulation);
			}
			list_forest_position_destroy(&lfp);
		}

		void list_forest_fprint ( FILE * file,
			list_forest lf,
			void ( * print_value ) ( FILE * , void * ) ,
			void ( * print_element ) ( FILE * , void * ) ) {
				list_forest_fprint_aux(file, lf, print_value, print_element, 0);

		}
